(0) Obligation:
Runtime Complexity TRS:
The TRS R consists of the following rules:
f4(S(x''), S(x'), x3, x4, S(x)) → f2(S(x''), x', x3, x4, x)
f4(S(x'), 0, x3, x4, S(x)) → f3(x', 0, x3, x4, x)
f2(x1, x2, S(x''), S(x'), S(x)) → f5(x1, x2, S(x''), x', x)
f2(x1, x2, S(x'), 0, S(x)) → f3(x1, x2, x', 0, x)
f4(S(x'), S(x), x3, x4, 0) → 0
f4(S(x), 0, x3, x4, 0) → 0
f2(x1, x2, S(x'), S(x), 0) → 0
f2(x1, x2, S(x), 0, 0) → 0
f0(x1, S(x'), x3, S(x), x5) → f1(x', S(x'), x, S(x), S(x))
f0(x1, S(x), x3, 0, x5) → 0
f6(x1, x2, x3, x4, S(x)) → f0(x1, x2, x4, x3, x)
f5(x1, x2, x3, x4, S(x)) → f6(x2, x1, x3, x4, x)
f3(x1, x2, x3, x4, S(x)) → f4(x1, x2, x4, x3, x)
f1(x1, x2, x3, x4, S(x)) → f2(x2, x1, x3, x4, x)
f6(x1, x2, x3, x4, 0) → 0
f5(x1, x2, x3, x4, 0) → 0
f4(0, x2, x3, x4, x5) → 0
f3(x1, x2, x3, x4, 0) → 0
f2(x1, x2, 0, x4, x5) → 0
f1(x1, x2, x3, x4, 0) → 0
f0(x1, 0, x3, x4, x5) → 0
Rewrite Strategy: INNERMOST
(1) CpxTrsToCpxRelTrsProof (BOTH BOUNDS(ID, ID) transformation)
Transformed TRS to relative TRS where S is empty.
(2) Obligation:
Runtime Complexity Relative TRS:
The TRS R consists of the following rules:
f4(S(x''), S(x'), x3, x4, S(x)) → f2(S(x''), x', x3, x4, x)
f4(S(x'), 0, x3, x4, S(x)) → f3(x', 0, x3, x4, x)
f2(x1, x2, S(x''), S(x'), S(x)) → f5(x1, x2, S(x''), x', x)
f2(x1, x2, S(x'), 0, S(x)) → f3(x1, x2, x', 0, x)
f4(S(x'), S(x), x3, x4, 0) → 0
f4(S(x), 0, x3, x4, 0) → 0
f2(x1, x2, S(x'), S(x), 0) → 0
f2(x1, x2, S(x), 0, 0) → 0
f0(x1, S(x'), x3, S(x), x5) → f1(x', S(x'), x, S(x), S(x))
f0(x1, S(x), x3, 0, x5) → 0
f6(x1, x2, x3, x4, S(x)) → f0(x1, x2, x4, x3, x)
f5(x1, x2, x3, x4, S(x)) → f6(x2, x1, x3, x4, x)
f3(x1, x2, x3, x4, S(x)) → f4(x1, x2, x4, x3, x)
f1(x1, x2, x3, x4, S(x)) → f2(x2, x1, x3, x4, x)
f6(x1, x2, x3, x4, 0) → 0
f5(x1, x2, x3, x4, 0) → 0
f4(0, x2, x3, x4, x5) → 0
f3(x1, x2, x3, x4, 0) → 0
f2(x1, x2, 0, x4, x5) → 0
f1(x1, x2, x3, x4, 0) → 0
f0(x1, 0, x3, x4, x5) → 0
S is empty.
Rewrite Strategy: INNERMOST
(3) SlicingProof (LOWER BOUND(ID) transformation)
Sliced the following arguments:
f5/1
f5/3
f0/0
f0/2
f0/4
f6/0
f6/3
(4) Obligation:
Runtime Complexity Relative TRS:
The TRS R consists of the following rules:
f4(S(x''), S(x'), x3, x4, S(x)) → f2(S(x''), x', x3, x4, x)
f4(S(x'), 0, x3, x4, S(x)) → f3(x', 0, x3, x4, x)
f2(x1, x2, S(x''), S(x'), S(x)) → f5(x1, S(x''), x)
f2(x1, x2, S(x'), 0, S(x)) → f3(x1, x2, x', 0, x)
f4(S(x'), S(x), x3, x4, 0) → 0
f4(S(x), 0, x3, x4, 0) → 0
f2(x1, x2, S(x'), S(x), 0) → 0
f2(x1, x2, S(x), 0, 0) → 0
f0(S(x'), S(x)) → f1(x', S(x'), x, S(x), S(x))
f0(S(x), 0) → 0
f6(x2, x3, S(x)) → f0(x2, x3)
f5(x1, x3, S(x)) → f6(x1, x3, x)
f3(x1, x2, x3, x4, S(x)) → f4(x1, x2, x4, x3, x)
f1(x1, x2, x3, x4, S(x)) → f2(x2, x1, x3, x4, x)
f6(x2, x3, 0) → 0
f5(x1, x3, 0) → 0
f4(0, x2, x3, x4, x5) → 0
f3(x1, x2, x3, x4, 0) → 0
f2(x1, x2, 0, x4, x5) → 0
f1(x1, x2, x3, x4, 0) → 0
f0(0, x4) → 0
S is empty.
Rewrite Strategy: INNERMOST
(5) DecreasingLoopProof (EQUIVALENT transformation)
The following loop(s) give(s) rise to the lower bound Ω(n1):
The rewrite sequence
f4(S(x'), 0, x3, x4, S(S(x14806_7))) →+ f4(x', 0, x4, x3, x14806_7)
gives rise to a decreasing loop by considering the right hand sides subterm at position [].
The pumping substitution is [x' / S(x'), x14806_7 / S(S(x14806_7))].
The result substitution is [x3 / x4, x4 / x3].
(6) BOUNDS(n^1, INF)